1. Field of the Invention
The present invention relates to a Viterbi decoder for decoding a convolution code.
2. Description of the Prior Art
A Viterbi decoding is an algorithm in which a path located at the minimum distance from a received series is selected from between two paths which are joined and a maximum likelihood decoding using a convolution code is efficiently executed. According to the Viterbi decoding, a correcting capability for random errors which are generated in a channel is high and if the Viterbi decoding is combined with a soft decision demodulation system, a particularly large coding gain can be obtained. Therefore, in a satellite communication system which is easily influenced by an interference wave and in which an electric power limitation is severe, a convolution code is used as an error correction code and a Viterbi decoder is used for decoding the convolution code. Details of the Viterbi algorithm are described in G. D. Forney. JR.; "The Viterbi Algorithm", PROCEEDING OF THE IEEE, Vol. 61, No. 3, March 1978, pp. 268-278, for instance.
The Viterbi decoding algorithm will be simply described.
For instance, consideration will be made with respect to a convolution code in which generating polynomials are given by EQU G.sub.1 (D)=1+D.sup.2 EQU G.sub.2 (D)=1+D+D.sup.2
and a coding ratio R is set to R=1/2 and a restriction length K is set to K=3. As shown in FIG. 1, an encoder for generating such a code can be constructed by: a shift register comprising registers 151A and 151B; and adders 152A, 152B, and 152C for addition of modulo 2.
As states (b.sub.1 b.sub.2) of the shift register in such an encoder, four states of (00), (01), (10), and (11) can be used. The number of states which can cause a transition when an input is given is always set to two.
That is, in the case of the state (00), when the input is set to 0, a transition to the state (00) occurs and when the input is set to 1, a transition to the state (01) occurs. In the case of the state (01), when the input is set to 0, a transition to the state (10) occurs and when the input is set to 1, a transition to the state (11) occurs. In the case of the state (10) when the input is set to 0, a transition to the state (00) occurs and when the input is set to 1, a transition to the state (01) occurs. In the case of the state (11) when the input is set to 0, a transition to the state (10) occurs and when the input is set to 1, a transition to the state (11) occurs.
Such state transitions are as shown in a trellis diagram of FIG. 2. In FIG. 2, a branch of a solid line denotes the transition by the input 0 and a branch of a broken line denotes the transition by the input 1. A numeral written along the branch denotes a code (G.sub.1 G.sub.2) which is output when the transition of the branch occurred.
As will be understood from FIG. 2, two paths are certainly joined in each state. According to the Viterbi decoding algorithm, the maximum likelihood path between two paths in each state is selected and, when a surviving path is selected up to a predetermined length, the maximum likelihood path among the paths selected in the respective state is detected, thereby decoding the received code.
The Viterbi decoder for decoding a convolution code on the basis of such a Viterbi algorithm fundamentally comprises: branch metric calculating means for calculating metrics between a reception series and each branch; ACS (Add-Compare-Select) calculating means for selecting a surviving path and calculating a state metric of a surviving path; state metric memory means for storing values of the state metrics in each state; a path memory for storing an estimated output of the selected path; and maximum likelihood deciding means for detecting an address of the maximum likelihood state metric and controlling the path memory.
In such a Viterbi decoder, the sum of the metrics of the selected path is stored into the state metric memory means. Therefore, there is a possibility such that the state metric memory means overflows. The normalization of metrics is executed to prevent the overflow of the state metric memory means as mentioned above.
That is, FIG. 3 shows an example of a conventional Viterbi decoder. In FIG. 3, a reception code which was soft decided to for instance, eight values is supplied to an input terminal 101. The reception code is supplied from the input terminal 101 to branch metric calculating means 102.
Four branch metrics between the reception series and each branch are obtained by the branch metric calculating means 102. The four branch metrics correspond to the likelihoods between the reception code and the codes (00), (01), (10), and (11), respectively.
An output of the branch metric calculating means 102 is supplied to ACS calculating means 103. State metrics which have been obtained until the preceding time are given from state metric memory means 104 to the ACS calculating means 103.
A surviving path in each state is selected by the ACS calculating means 103 in accordance with the state metric transition diagram. The state metric of the surviving path is calculated. The state metric transition diagram is formed on the basis of the trellis diagram.
In the case of using codes shown in a trellis diagram as shown in FIG. 2, state metric transition diagrams as shown in FIGS. 4A and 4B are obtained.
That is, for instance, in the case of the trellis diagram shown in FIG. 2, two kinds of a path which is caused by outputting the code (00) from the state (00) and a path which causes the code (11) from the state (10) are joined in the state (00). Therefore, the present state metric SM00(new) becomes ##EQU1## On the other hand, two kinds of a path which causes the code (11) from the state (00) and a path which causes the code (00) from the state (10) are joined in the state (01). Therefore, the present state metric SM01(new) becomes ##EQU2##
Two kinds of a path which is caused by outputting the code (01) from the state (01) and a path which causes the code (10) from the state (11) are joined in the state (10). Therefore, the present state metric SM10(new) becomes ##EQU3##
On the other hand, two kinds of a path which causes the code (10) from the state (01) and a path which causes the code (01) from the state (11) are joined in the state (11). Therefore, the present state metric SM11(new) becomes ##EQU4## On the basis of the above points, as shown in FIGS. 4A and 4B, state metric transition diagrams can be formed.
In FIG. 3, an output of the ACS calculating means 103 is supplied to normalizing means 105 and is also supplied to maximum likelihood value detecting means 106. An output of the normalizing means 105 is supplied to the state metric memory means 104. On the other information signal regarding the selected path is output from the ACS calculating means 103. The information signal is sent to a path memory 107.
The maximum likelihood value detecting means 106 detects the maximum likelihood state metric among the present state metrics which are output from the ACS calculating means 103.
The maximum likelihood state metric is supplied to the normalizing means 105. In the normalizing means 105, the maximum likelihood state metric is subtracted from each of the state metrics. Due to this, the state metrics are normalized, thereby preventing that the state metric memory means 104 overflows.
An output of the maximum likelihood value detecting means 106 is supplied to maximum likelihood deciding means 108. After the surviving path of a predetermined length was selected, the maximum likelihood path in each state is detected by the maximum likelihood deciding means 108. The path memory 107 is controlled by an output of the maximum likelihood deciding means 108 and the reception code is decoded.
In the case of such a construction, since the normalization is executed by using the present maximum likelihood state metric detected by the maximum likelihood value detecting means 106, the value of the maximum likelihood state metric after completion of the normalization can be certainly set to a predetermined value (for instance, 0.)
However, in the conventional Viterbi decoder constructed as mentioned above, the present maximum likelihood state metric is detected by the maximum likelihood value detecting means 106, the state metrics are normalized by using the present maximum likelihood state metric, and after completion of such a normalizing process, a process to store the state metrics into the state metric memory means 104 must be executed. Thus, a long calculating time is needed.
Therefore, a Viterbi decoder in which metrics are normalized by using the preceding maximum likelihood state metric has been proposed. If the preceding maximum likelihood state metric is used, the state metrics can be normalized without waiting for the detecting process of the present maximum likelihood state metric and the processing speed can be improved.
On the other hand, as shown in FIG. 5, there has been proposed a system in which the preceding maximum likelihood state metric is obtained and given to normalizing means 125 provided before an ACS calculating means 123, thereby executing the normalizing process (for instance, Japanese Patent Laid Open Publication No. Sho 59-19454).
That is, in FIG. 5, a reception code is supplied from an input terminal 121 and a branch metric is obtained by branch metric calculating means 122. The branch metric is supplied to the normalizing means 125. The maximum likelihood value of the preceding state metric is supplied from maximum likelihood value memory means 129 to the normalizing means 125.
In the normalizing means 125, the maximum likelihood value of the preceding state metric is subtracted from a branch metric. An output of the normalizing means 125 is supplied to the ACS calculating means 123. An output of state metric memory means 124 is supplied to the ACS calculating means 123. In the ACS calculating means 123, a surviving path in each state is selected in accordance with the state metric transition diagram and the state metric of the surviving path is calculated.
An output of the ACS calculating means 123 is supplied to the state metric memory means 124 and is also supplied to maximum likelihood value detecting means 126. On the other hand, an output of the ACS calculating means 123 is given to a path memory 127.
In the maximum likelihood value detecting means 126, the maximum likelihood value of the state metric is obtained. The state metric is supplied to the maximum likelihood value memory means 129 and is also supplied to maximum likelihood deciding means 128. An output of the maximum likelihood value memory means 129 is supplied to the normalizing means 125. In the normalizing means 125, the metrics are normalized by using the maximum likelihood value of the preceding state metrics stored in the maximum likelihood value memory means 129.
However, if the normalizing process of the state metrics is executed by using the preceding maximum likelihood state metrics, the value of the maximum likelihood state metric after completion of the nomalization is not set to a predetermined value (for example, 0). If the value of the maximum likelihood state metric is always set to a predetermined value (for instance, 0), by searching the state metric of such a value, the address of the state metric can be detected, so that the address of the maximum likelihood state metric can be very easily detected. However, if the value of the maximum likelihood state metric is not set to a predetermined value, it is necessary to execute processes such as to compare the respective state metrics and detect the maximum likelihood state metric.
As mentioned above, if the present maximum likelihood state metric is obtained from an output after completion of the ACS calculation and the state metrics are nomalized by using it, a problem such that a long processing time is needed occurs.
On the other hand, if the normalization is executed by using the maximum likelihood value of the preceding state metric, since the maximum likelihood value is not set to a precetermined value, there occur problems such that the precesses to detect the maximum likelihood state metric and its address become complicated and the circuit scale increases.